import java.util.*;

public class Solution {

    /**
     * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
     * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
     */
    //0b01111111_11111111_11111111_11111111
    public static final int b01_06 = 0b00000000_00000000_00000000_00111111;
    public static final int b07_15 = 0b00000000_00000000_01111111_11000000;
    public static final int b16_24 = 0b00000000_11111111_10000000_00000000;
    public static final int b25_31 = 0b01111111_00000000_00000000_00000000;
    public static final int SIZE = 512;

    public static int firstMissingPositive(int[] nums) {
        Group storage = new Group();
        storage.set(split(0),0);
        for (int n : nums) {
            if (n < 1) {
                continue;
            }
            storage.set(split(n), 0);
        }
        return storage.getMinNum(0);
    }

    private static int[] split(int i) {
        int[] result = new int[4];
        result[3] = i & b01_06;
        result[2] = (i & b07_15) >> 6;
        result[1] = (i & b16_24) >> 15;
        result[0] = (i & b25_31) >> 24;
        return result;
    }

    private static class Group {
        private Group[] arr = new Group[SIZE];
        private long value = 0L;

        private void set(int[] values, int index) {
            int v = values[index];
            if (index == 3) {
                this.value |= (1L << v);
                return;
            }
            Group group = arr[v];
            if (Objects.isNull(group)) {
                group = new Group();
                arr[v] = group;
            }
            group.set(values, index + 1);
        }

        private int getMinNum(int index) {
            if (index == 3) {
                if (value == -1) {
                    return -1;
                } else {
                    for (int r = 0; r < 64; r++) {
                        if (((value >> r) & 1) == 1) {
                            continue;
                        }
                        return r;
                    }
                }
            }

            for (int i = 0; i < arr.length; i++) {
                Group g = arr[i];
                if (g == null) {
                    return trans(i, index);
                } else {
                    int minNum = g.getMinNum(index + 1);
                    if (minNum > -1) {
                        return trans(i, index) | minNum;
                    }
                }
            }
            return -1;
        }
    }

    private static int trans(int value, int index) {
        switch (index) {
            case 0:
                return value << 24;
            case 1:
                return value << 15;
            case 2:
                return value << 6;
            default:
                return 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{99,94,96,11,92,5,91,89,57,85,66,63,84,81,79,61,74,78,77,30,64,13,58,18,70,69,51,12,32,34,9,43,39,8,1,38,49,27,21,45,47,44,53,52,48,19,50,59,3,40,31,82,23,56,37,41,16,28,22,33,65,42,54,20,29,25,10,26,4,60,67,83,62,71,24,35,72,55,75,0,2,46,15,80,6,36,14,73,76,86,88,7,17,87,68,90,95,93,97,98};
        int i = firstMissingPositive(nums);
        System.out.println(i);
    }

}